package com.hqq.exercise.list;

/**
 * ComplexListClone 复杂链表的复制
 * 题目描述:
 * 实现函数复制一个复杂链表。
 * 在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个指向链表中任意结点或null[厉害了QAQ]
 * Created by heqianqian on 2017/8/14.
 */
public class ComplexListClone<T> {

    /**
     * 复制一个复杂链表
     *
     * @param head 复杂链表的头节点
     * @return 复制的链表
     */
    public ComplexListNode<T> cloneComplexList(ComplexListNode<T> head) {
        cloneNodes(head);
        addRandomNext(head);
        return splitList(head);
    }

    /**
     * 将链表分成两个链表
     */
    private ComplexListNode<T> splitList(ComplexListNode<T> head) {
        ComplexListNode<T> node = head;
        ComplexListNode<T> cloneHead = null;//用来标识复制链表的头结点
        ComplexListNode<T> cloneNode = null;

        if (node != null) {
            cloneHead = node.nextNode;
            cloneNode = cloneHead;
            node.nextNode = cloneNode.nextNode;
            node = node.nextNode;
        }

        while (node != null) {
            cloneNode.nextNode = node.nextNode;
            cloneNode = cloneHead.nextNode;
            node.nextNode = cloneNode.nextNode;
            node = node.nextNode;
        }
        return cloneHead;
    }

    /**
     * 新复制节点添加随机指针
     */
    private void addRandomNext(ComplexListNode<T> head) {
        ComplexListNode<T> node = head;
        while (node != null) {
            ComplexListNode<T> cloneNode = node.nextNode;
            if (node.randomNode != null) {
                cloneNode.randomNode = node.randomNode.nextNode;
            }
            node = cloneNode.nextNode;
        }
    }


    /**
     * 复制节点并相应的插入到原节点后面
     */
    private void cloneNodes(ComplexListNode<T> head) {
        ComplexListNode<T> node = head;
        while (node != null) {
            ComplexListNode<T> cloneNode = new ComplexListNode<>(head.data);
            cloneNode.nextNode = node.nextNode;
            node.nextNode = cloneNode;
            node = cloneNode.nextNode;
        }
    }
}
